package style.zcyLeetCode.a_0003_详解桶排序以及排序内容大总结;

import java.util.Arrays;

/**
 * 堆排序
 * <p>
 * 3 5 2 7 1 9 6 数值
 * 0 1 2 3 4 5 6 下标
 * <p>
 * 下标表示
 * 0
 * 1   2
 * 3 4 5 6
 * <p>
 * index
 * 左子树  2*i+1
 * 右子数  2*i+2
 * 父节点  (i-1)/2
 */

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 2, 4, 7};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // 保证整体是大顶堆
        // 方法一、
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }
        // 方法二、
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }


        // 最大值跟末尾值做交换 保证最后一个是最大值，依次下去
        int size = arr.length;
        swap(arr, 0, --size);
        while (size > 0) {
            // 继续获取剩下的大顶堆
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    /**
     * 节点插入
     *
     * @param arr
     * @param index
     */
    private static void heapInsert(int[] arr, int index) {
        // 判断插入的节点跟他的父节点大小，大则交换 循环下去
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    /**
     * 某个数在index的位置，能否往下移动
     *
     * @param arr
     * @param index
     * @param size
     */
    private static void heapify(int[] arr, int index, int size) {
        int left = index * 2 + 1;  // 左孩子的下标

        while (left < size) {
            // 两个孩子中，谁的值大，就把下标给larest
            int largest = left + 1 < size && arr[left + 1] > arr[left]
                    ? left + 1
                    : left;
            // 父和子之间，谁的值大，就把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}
